package com.company.ljh.easy;
//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
// 子数组 是数组中的一个连续部分。
//
//
//
// 示例 1：
//
//
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
//
//
// 示例 2：
//
//
//输入：nums = [1]
//输出：1
//
//
// 示例 3：
//
//
//输入：nums = [5,4,-1,7,8]
//输出：23
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 105
// -104 <= nums[i] <= 104
//
//
//
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
// Related Topics 数组 分治 动态规划
// 👍 4573 👎 0

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2022/3/21 17:06
 * @version:1.0
 */
public class 最大数组和 {
    /**
     * 思路:1.前面数字的和大于0，结果保留，小于0，去掉
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i : nums) {
            if (sum >= 0) {
                sum += i;
            } else {
                sum = i;
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }



    class status{
        //以左节点开始的最大和
        private int lsum;
        //以右节点开始的最大和
        private int rsum;
        //区间的和
        private int isum;
        //区间最大子段和
        private int msum;
        public status(int lsum,int rsum,int isum,int msum){
            this.lsum = lsum;
            this.rsum = rsum;
            this.isum = isum;
            this.msum = msum;
        }
    }
    /**
     * 思路:2.分治法，线段树
     * 我们定义一个操作 get(a, l, r) 表示查询 aa 序列 [l,r][l,r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l,r][l,r]，我们取 m = \lfloor \frac{l + r}{2} \rfloorm=⌊
     * 2
     * l+r
     * ​
     * ⌋，对区间 [l,m][l,m] 和 [m+1,r][m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 11 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l,m][l,m] 区间的信息和 [m+1,r][m+1,r] 区间的信息合并成区间 [l,r][l,r] 的信息。最关键的两个问题是：
     * <p>
     * 我们要维护区间的哪些信息呢？
     * 我们如何合并这些信息呢？
     * 对于一个区间 [l,r][l,r]，我们可以维护四个量：
     * <p>
     * \textit{lSum}lSum 表示 [l,r][l,r] 内以 ll 为左端点的最大子段和
     * \textit{rSum}rSum 表示 [l,r][l,r] 内以 rr 为右端点的最大子段和
     * \textit{mSum}mSum 表示 [l,r][l,r] 内的最大子段和
     * \textit{iSum}iSum 表示 [l,r][l,r] 的区间和
     * 以下简称 [l,m][l,m] 为 [l,r][l,r] 的「左子区间」，[m+1,r][m+1,r] 为 [l,r][l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l,r][l,r] 的信息）？对于长度为 11 的区间 [i, i][i,i]，四个量的值都和 \textit{nums}[i]nums[i] 相等。对于长度大于 11 的区间：
     * <p>
     * 首先最好维护的是 \textit{iSum}iSum，区间 [l,r][l,r] 的 \textit{iSum}iSum 就等于「左子区间」的 \textit{iSum}iSum 加上「右子区间」的 \textit{iSum}iSum。
     * 对于 [l,r][l,r] 的 \textit{lSum}lSum，存在两种可能，它要么等于「左子区间」的 \textit{lSum}lSum，要么等于「左子区间」的 \textit{iSum}iSum 加上「右子区间」的 \textit{lSum}lSum，二者取大。
     * 对于 [l,r][l,r] 的 \textit{rSum}rSum，同理，它要么等于「右子区间」的 \textit{rSum}rSum，要么等于「右子区间」的 \textit{iSum}iSum 加上「左子区间」的 \textit{rSum}rSum，二者取大。
     * 当计算好上面的三个量之后，就很好计算 [l,r][l,r] 的 \textit{mSum}mSum 了。我们可以考虑 [l,r][l,r] 的 \textit{mSum}mSum 对应的区间是否跨越 mm——它可能不跨越 mm，也就是说 [l,r][l,r] 的 \textit{mSum}mSum 可能是「左子区间」的 \textit{mSum}mSum 和 「右子区间」的 \textit{mSum}mSum 中的一个；它也可能跨越 mm，可能是「左子区间」的 \textit{rSum}rSum 和 「右子区间」的 \textit{lSum}lSum 求和。三者取大。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int fzf(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i : nums) {
            if (sum >= 0) {
                sum += i;
            } else {
                sum = i;
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
    private status getStatus(int nums[], int l, int r){
        int lsum = 0;
        int rsum =0;
        int isum = 0;
        int msum = 0;
        if (l == r){
            //数组长度为1
            lsum = nums[l];
            rsum = nums[l];
            isum = nums[l];
            msum = nums[l];
            status status = new status(lsum,rsum,isum,msum);
            return  status;
        }
        int midle = (l+r)/2;
        status lstatus = getStatus(nums, l, midle);
        status rstatus = getStatus(nums, midle+1, r);
        //lsum的值为左半部分的lsum或者左半部分的isum+右半部分的lsum
        lsum = Math.max(lstatus.lsum,lstatus.isum+rstatus.lsum);
        //rsum的值为右半部分的rsum或者右半部分的isum+左半部分的rsum
        rsum = Math.max(rstatus.rsum,rstatus.isum+lstatus.rsum);
        //isum的值为左半部分的isum+右半部分的isum
        isum = lstatus.isum+rstatus.isum;

        return new status(lsum,rsum,isum,msum);
    }

    public static void main(String[] args) {
        最大数组和 z = new 最大数组和();
        int num[]= new int[]{-2,1};
        status status = z.getStatus(num, 0, num.length - 1);
        System.out.println(status.msum);
    }
}
